package leetcode.dynamic;

public class Lc494 {


    //设nums中正数的和为P,要减去的数和为N，所有nums的数和为sum，则有：
    //P + N = S
    //P - N = T（target）
    //2P = S + T => P = (S + T) / 2 原问题就转换成了装满一个大小为P的背包有多少方案
    //dp[i][j]代表在前i个物品中，装满j空间的方案数，则有
    //dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i]]
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if ((sum + target) % 2 != 0)
            return 0;
        int pack = (sum + target) / 2;
        if (pack < 0)
            return 0;
        int[][] dp = new int[nums.length + 1][pack + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= pack ; j++) {
                if (nums[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[nums.length][pack];
    }




}
